import java.util.Stack;

public class LC_20 {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        int i = 0;
        while(i < s.length()){
            char ch1 = s.charAt(i);
            if(ch1 == '(' || ch1 == '[' || ch1 == '{'){
                stack.push(ch1);
            }else{
                if(stack.empty()){
                    return false;
                }
                char ch2 = stack.pop();
                if((ch1 == ')' && ch2 != '(') ||
                        (ch1 == ']' && ch2 != '[') ||
                        (ch1 == '}' && ch2 != '{')) {
                    return false;
                }
            }
            i++;
        }
        return stack.empty();
    }
}
